package com.major.dawn.leetCode.sort;

public class QuickSort {

    public static int[] sortArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        quickSort(arr, left, right);

        return arr;
    }

    private static void quickSort(int[] arr, int left, int right) {

        int begin = left;
        int end = right;
        if (right > left) {
            int startingPoint = arr[left];
            while (end > begin) {
                while (end > begin && arr[end] > startingPoint) {

                    end--;
                }
                if (end > begin) {
                    arr[begin] = arr[end];
                    begin++;
                }

                while (end > begin && arr[begin] < startingPoint) {
                    begin++;
                }

                if (end > begin) {
                    arr[end] = arr[begin];
                    end--;
                }

            }

            arr[begin] = startingPoint;
            quickSort(arr, left, begin - 1);
            quickSort(arr, begin + 1, right);
        }
    }


    public static void main(String[] args) {

        int[] ints = QuickSort.sortArray(new int[]{5, 2, 3, 1});
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }

    }


}
